/*
 * sequencelist.h
 * 线性表的动态分配顺序存储结构。
 * 此结构和书中的结构类似，不同之处在于，其数组空间只记录了首地址，可在数组的空间不够时，再次动态分配空间。
 * 当然，在当前代码中，并未书写此部分代码，有兴趣的同学可做扩展。
 *  Created on: 2017年3月20日
 *      Author: deng.zhao
 */

#ifndef SEQUENCELIST_H_
#define SEQUENCELIST_H_

/* 线性表存储空间的初始分配量 */
#define LIST_INIT_SIZE 10
/* 线性表存储空间的分配增量 */
#define LIST_INCREMENT 2

/*
 * 顺序表。
 */
typedef struct
{
	// 存储空间基址；
	ElementType* elem;
	// 当前长度；
	int length;
	// 当前容量；
	int listsize;
} SequenceList;

/*
 * 构造一个空的顺序线性表。
 */
Status InitList(SequenceList* lp)
{
	// 动态为顺序表中的数组分配空间；
	lp->elem = (ElementType*) malloc(LIST_INIT_SIZE * sizeof(ElementType));
	// 判断空间是否分配成功；
	if (lp->elem)
	{	// 若成功；
		// 初始化顺序表长度为0；
		lp->length = 0;
		// 初始化顺序表容量为常量LIST_INIT_SIZE；
		lp->listsize = LIST_INIT_SIZE;
		return OK;
	}
	else
	{	// 若失败；
		// 退出，并报告状态码为OVERfLOW；
		exit(OVERFLOW);
	}
}

/*
 * 销毁顺序线性表。
 */
Status DestoryList(SequenceList* lp)
{
	// 释放顺序表中的数组空间；
	free(lp->elem);
	// 将顺序表的数组空间基址置为空；
	lp->elem = NULL;
	// 将顺序表的长度置为0；
	lp->length = 0;
	// 将顺序表容量置为0；
	lp->listsize = 0;

	return OK;
}

/*
 * 重置顺序线性表为空表；
 */
Status ClearList(SequenceList* lp)
{
	// 将顺序表容量置为0；
	lp->length = 0;

	return OK;
}

/*
 * 判断顺序线性表是否为空，
 */
Boolean IsEmptyList(SequenceList* lp)
{
	return lp->length == 0 ? TRUE : FALSE;
}

/*
 * 获取顺序线性表中的元素个数；
 */
int ListLength(SequenceList* lp)
{
	return lp->length;
}

/*
 * 在顺序线性表的指定位置之前，加入元素；
 * 此函数可做进一步扩展，在空间不足时，再次动态分配空间。
 */
Status ListInsert(SequenceList* lp, int location, ElementType elem)
{
	int i;
	// 判断给定的位置是否合法；
	if (location < 1 || location > lp->length + 1)
	{	// 若不合法
		return ERROR;
	}

	// 判断顺序表的存储空间是否已满。
	if (lp->listsize <= lp->length)
	{	// 若存储空间已满；
		// 返回状态值（也可调整为动态增加容量）；
		return INFEASIBLE;
	}

	// 元素依次后移；
	for (i = lp->length + 1; i >= location; i--)
	{
		lp->elem[i] = lp->elem[i - 1];
	}

	// 加入元素；
	lp->elem[location - 1] = elem;
	// 顺序表长度增加；
	lp->length++;

	return OK;
}

/*
 * 在顺序线性表的尾部，加入元素。
 */
Status ListAppend(SequenceList* lp, ElementType elem)
{
	// 调用加入元素的函数，固定其位置为尾部；
	return ListInsert(lp, (lp->length) + 1, elem);
}

/*
 * 在顺序线性表的指定位置删除元素；
 */
Status ListDelete(SequenceList* lp, int location)
{
	int i;
	// 判断给定的位置是否合法；
	if (location < 1 || location > lp->length)
	{	// 若不合法
		return ERROR;
	}

	// 元素依次前移；
	for (i = location; i < lp->length; i++)
	{
		lp->elem[i-1] = lp->elem[i];
	}
	// 顺序表长度減少；
	lp->length--;

	return OK;
}

/*
 * 在顺序线性表中找到给定元素，并返回其位置，如果找不到，则返回0；
 * 使用函数指针，以便在对不同类型元素判等时能完成操作。
 */
int LocateElem(SequenceList* lp, ElementType elem,
		Status (*equals)(ElementType, ElementType))
{
	int i;
	for (i = 0; i < lp->length; i++)
	{
		if (equals(lp->elem[i], elem))
		{
			return i + 1;
		}
	}

	return 0;
}

/*
 * 遍历顺序线性表。
 * 使用函数指针，以便在对不同类型元素进行访问操作时能完成操作。
 */
Status ListTraverse(SequenceList* lp, void (*visit)(ElementType))
{
	int i;
	for (i = 0; i < lp->length; i++)
	{
		visit(lp->elem[i]);
		printf("\n");
	}
	printf("\n");

	return OK;
}

#endif /* SEQUENCELIST_H_ */
